package geekstudy.week4;

/**
 *
 *  https://leetcode-cn.com/problems/delete-node-in-a-bst/
 * 450. 删除二叉搜索树中的节点
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
 * 内存消耗：39 MB, 在所有 Java 提交中击败了32.72% 的用户
 *
 */
public class Week4DeleteNodeInABST {

    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) {
            return null;
        }

        if(key < root.val) {
            root.left = deleteNode(root.left, key);
            return root;
        } else if(key > root.val) {
            root.right = deleteNode(root.right, key);
            return root;
        } else if(key == root.val) {
            if(root.left == null) {
                return root.right;
            } else if(root.right == null) {
                return root.left;
            } else {
                TreeNode rightMin = min(root.right);
                rightMin.right = deleteMin(root.right);
                rightMin.left = root.left;
                return rightMin;
            }
        } else {
            return root;
        }

    }

    private TreeNode min(TreeNode node) {
        if(node.left == null) {
            return node;
        }
        return min(node.left);
    }

    private TreeNode deleteMin(TreeNode node) {
        if(node.left == null) {
            return node.right;
        }
        node.left = deleteMin(node.left);
        return node;
    }
}
